1. Field of the Invention
This invention relates generally to a filter for filtering high frequency noise from a signal, such as, a radio altimeter signal and, more particularly, to a fast median filter for filtering high frequency noise from a signal while preserving sharp edges in the signal by sorting a finite set of data points of the signal to determine the median of the set of data points without shifting or moving the data points in memory.
2. Description of the Prior Art
Radio altimeters are instruments that provide an indication of the distance of an aircraft above the terrain. These devices measure the time it takes for a radio signal at about 4300 mHz to travel from the aircraft to and from the terrain being overflown. If the terrain was a perfectly flat horizontal plane, mirror-like reflection of the radio signal would result. In this situation, the distance of the aircraft above the terrain could be measured exactly. However, the terrain is not perfectly flat, which results in scattering of the radio signal, consequently causing high frequency noise components in the radio altitude signal.
There have been various attempts in the art, both analog and digital, to provide a suitable filter for filtering high frequency noise from a radio altimeter signal. An example of an analog filter is disclosed in U.S. Pat. No. 3,715,718 to Astengo, which is assigned to the same assignee as the assignee of the present invention. In Astengo, a radio altitude rate signal and a barometric altitude rate signal are applied to a complementary filter, comprised of a high pass filter and a low pass filter. The radio altitude rate signal is applied to the low pass filter for removing high frequency noise components, while the barometric altitude rate signal is applied to the high pass filter. The outputs of the filters are combined to provide a composite signal. The complementary filter, disclosed in Astengo, overcomes earlier encountered problems which attempted to remove high frequency noise components from radio altitude or radio altitude rate signals with analog filters. In those systems, low pass filters alone were used with sufficiently high time constants to remove high frequency noise. However, such filters provided an unsuitable response time to actual changes in the radio altitude. Although this problem is overcome in Astengo through the use of composite signal, such a system, among other things, also requires the use of a barometric altitude rate signal.
There are also various digital techniques for filtering noisy signals, such as, radio altitude or radio altitude rate signals, both linear and non-linear. One technique is known as a mean filter. Mean filters are linear filters which provide the linear average of a signal applied to its input. While mean filters may be suitable in some applications, they provide unsatisfactory results for signals which have sharp edges. A radio altimeter will generate a signal with a sharp edge when the aircraft is flying over a steep cliff, ravine or the like. In such a situation, a mean filter will smooth out the signal edges as well as the noise. Consequently, mean filters provide unsatisfactory results when used with signals having sharp edges.
Another type of filter used in such applications is a median filter. Such filters and related filters are generally described in an article entitled, "Generalized Median Filtering and Related Non-Linear Filtering Techniques", published in IEEE Translations on Acoustics, Speech and Signal Processing, Vol. ASSP-33, No. 3, June 1985.
Median filters are non-linear filters, which determine the median signal value for a finite neighborhood around each data point. For example, for the following sequential data points: 22, 16, 19, 18, 17; the median is 18, while the linear mean is 18.4. The mean is obtained by adding all the data points and dividing the resulting sum by the total number of data points.
Median filters are well adapted to filtering impulsive and high frequency noise from signals, while preserving sharp signal edges. Median filters generally operate on a running array of, for example, 5 data points at a time. At each sample time, the group of 5 data points is sorted and the median determined. Some conventional median filters, sometimes call "bubblers", determine the median of an array by comparing each data point in succession with the data point immediately next to it and shifting the data point depending on the result of the comparison. Such conventional median filters involve a substantial amount of manipulation of the data in memory. Specifically, a substantial number of memory access and move operations are required. Consequently, such operations result in a substantial amount of processing time and therefore are not suitable for filtering data at high input rates, such as the data from a radio altimeter.